#include <vector>
#include <iostream>
using namespace std;
long mergeInversePairs(vector<int> &data,int min_idx,int mid_idx,int max_idx)
{
	long sum = 0;
	int lengthA = mid_idx-min_idx+1;
	int lengthB = max_idx - mid_idx;
	int dataA[lengthA],dataB[lengthB];
	for(int i = 0; i < lengthA ; ++i)
	{
		dataA[i] = data[min_idx+i];
	}
	for(int i = 0 ; i < lengthB ; ++i)
	{
		dataB[i] = data[mid_idx+1+i];
	}
	int idxA=lengthA-1,idxB=lengthB-1;
	int idx = max_idx;
	while(idxA >= 0 && idxB >= 0)
	{
		if(dataA[idxA] > dataB[idxB])
		{
			sum+= idxB+1;
			data[idx] = dataA[idxA];
			--idx;
			--idxA;
		}
		else
		{
			data[idx] = dataB[idxB];
			--idx;
			--idxB;
		}
	}
	while(idxA >= 0)
	{
		data[idx] = dataA[idxA];
		--idx;
		--idxA;
	}
	while(idxB >= 0)
	{
		data[idx]  = dataB[idxB];
		--idx;
		--idxB;
	}
	return sum;
}

long inversePairs(vector<int> &data,int min_idx,int max_idx)
{
	long sum = 0;
	if(min_idx+1 >= max_idx)
	{
		if(data[min_idx] > data[max_idx])
		{
			++sum;
			int temp = data[min_idx];
			data[min_idx] = data[max_idx];
			data[max_idx] = temp;
		}
		return sum;
	}
	int mid_idx = (min_idx + max_idx)/2;
	sum += inversePairs(data,min_idx,mid_idx);
	sum += inversePairs(data,mid_idx+1,max_idx);
	sum += mergeInversePairs(data,min_idx,mid_idx,max_idx);
	return sum;
}

int InversePairs(vector<int> data)
{	
	if(data.empty() || data.size() == 1)
		return 0;
	long result = inversePairs(data,0,data.size()-1);
	return result%1000000007;
}


int main()
{
	vector<int> data1{7,5,6,4};
	vector<int> data2{7,3,8,2,5,4,6,3,1};
	vector<int> data3{3,6};
	vector<int> data4{3};
	vector<int> data5{1,2,3,4,5,6,7,8};
	vector<int> data6{7,6,4,3,2,1};
	vector<int> data7;
	cout<<InversePairs(data1)<<endl;
	cout<<InversePairs(data2)<<endl;
	cout<<InversePairs(data3)<<endl;
	cout<<InversePairs(data4)<<endl;
	cout<<InversePairs(data5)<<endl;
	cout<<InversePairs(data6)<<endl;
	cout<<InversePairs(data7)<<endl;

	return 0;
}